package cn.corffen.test.algorithm.java;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BacktrackJava {


    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }
        int n = nums.length;
        backtrack(n, answer, output, 0);
        return answer;
    }

    private void backtrack(int n, List<List<Integer>> ans, List<Integer> output, int first) {
        if (first == n) {
            ans.add(new ArrayList<>(output));
            return;
        }
        for (int i = first; i < n; i++) {
            Collections.swap(output, i, first);
            backtrack(n, ans, output, first + 1);
            Collections.swap(output, i, first);
        }
    }
}
